package com.hx.base.others;

import java.util.Stack;

/**
 * 描述：
 *
 * @author Minghua Chen
 * @date 2021-05-15 11:56
 */
public class NoIncirveFunction {
    public static void main(String[] args) {
        int arg = 30;
        long start = System.currentTimeMillis();
        int fun = fun(arg);
        System.out.println(System.currentTimeMillis() - start);
        System.out.println(fun);
        long start1 = System.currentTimeMillis();
        int fun2 = func2(arg);
        System.out.println(System.currentTimeMillis() - start1);
        System.out.println(fun2);
    }

    public static int func2(int n) {

        Stack<Integer> stack = new Stack<>();
        for (int i = 1; i <= n; i++) {
            if (i <= 2) {
                stack.push(i);
            } else {
                Integer s2 = stack.pop();
                Integer s1 = stack.pop();
                Integer s3 = s1 + s2;
                stack.push(s2);
                stack.push(s3);
            }
        }

        return stack.pop();
    }


    public static int fun(int n) {

        if (n == 1 || n == 2) {
            return n;
        } else {
            return fun(n - 1) + fun(n - 2);
        }
    }
}
